package leetcode_1100;

import java.util.HashMap;
import java.util.Map;

public class LongestArithmeticSequence_1027 {
	public static void main(String[] args) {
		LongestArithmeticSequence_1027 test = new LongestArithmeticSequence_1027();
		System.out.println(test.longestArithSeqLength(new int[] {3,6,9,12}));
		System.out.println(test.longestArithSeqLength(new int[] {9,4,7,2,10}));
	}
	
	public int longestArithSeqLength(int[] A) {
		int max = 1;
        Map<Integer,Map<Integer,Integer>> dp = new HashMap<Integer,Map<Integer,Integer>>();
        for(int i=0;i<A.length;++i) {
        	Map<Integer,Integer> now = new HashMap<Integer,Integer>();
        	for(int j=0;j<i;++j) {
        		int diff = A[i]-A[j];
        		Map<Integer,Integer> pre = dp.get(j);
        		int i1 = pre.getOrDefault(diff, 1)+1;
        		now.put(diff, i1);
        		max = Math.max(max, i1);
        	}
        	dp.put(i, now);
        }
        return max;
    }
	
}
